home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / trafo.me < prev    next >
Text File  |  1992-09-25  |  63KB  |  1,873 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. .if t \{ \
  293. .pl 29.7c    \" page length
  294. .po 2.5c    \" page offset (left margin)
  295. .ll 16.5c    \" line length
  296. .lt 16.5c    \" title length
  297. .nr LL 16.5c
  298. .nr )l 29.7c
  299. .nr hm 2c
  300. .nr $r 9    \" factor for vertical spacing
  301. .nr $R \n($r
  302. .sz 12        \" font size
  303. .nr pp 12
  304. .nr sp 12
  305. .nr tp 12
  306. .nr fp 10
  307. .hc ~        \" hyphenation character
  308. .        \" Umlauts and sharp s
  309. .ds A \(A:
  310. .ds O \(O:
  311. .ds U \(U:
  312. .ds a \(a:
  313. .ds o \(o:
  314. .ds u \(u:
  315. .ds s \(ss
  316. .        \"  UMLAUT  \*:u, etc.
  317. .ds : \v'-0.6m'\h'(1u-(\\n(.fu%2u))*0.13m+0.06m'\z.\h'0.2m'\z.\h'-((1u-(\\n(.fu%2u))*0.13m+0.26m)'\v'0.6m'
  318. .\}
  319. .if n \{ \
  320. .po 0        \" page offset (left margin)
  321. .ll 78        \" line length
  322. .lt 78        \" title length
  323. .nr $r 4    \" factor for vertical spacing
  324. .nr $R \n($r
  325. .hc ~        \" hyphenation character
  326. .        \" Umlaute und scharfes s
  327. .ds A Ae
  328. .ds O Oe
  329. .ds U Ue
  330. .ds a ae
  331. .ds o oe
  332. .ds u ue
  333. .ds s sz
  334. .\}
  335. .de _
  336. \&\\$1\l'|0\(ul'\\$2
  337. ..
  338. .de FT        \" font for programs
  339. .ft C
  340. .sz -2
  341. ..
  342. .de FR
  343. .ft R
  344. .sz +2
  345. ..
  346. .de []        \" start to display collected references
  347. .uh References
  348. .lp
  349. ..
  350. .de $0        \" collect table of contents
  351. .(x
  352. .ta 2c
  353. .ie '\\$2''    \\$1
  354. .el \\$2.    \\$1
  355. .)x
  356. ..
  357. .de np
  358. .nr $p +1
  359. .ip \\n($p.
  360. ..
  361. .de SH
  362. .sp 0.5
  363. .in -3
  364. .r \\$1
  365. .sp 0.5
  366. .in +3
  367. ..
  368. .de PP
  369. .sp 0.5
  370. ..
  371. .de IP
  372. .ip \\$1 \\$2
  373. ..
  374. .de I
  375. .i \\$1
  376. ..
  377. .de TH
  378. ..
  379. .de SH
  380. .sp 0.5
  381. .in -3
  382. .r \\$1
  383. .sp 0.5
  384. .in +3
  385. ..
  386. .de I
  387. .i \\$1
  388. ..
  389. .EQ
  390. delim off
  391. .EN
  392. .hc ~
  393. .ds ], , 
  394. .b " "
  395. .sp 1c
  396. .ta 9c
  397. .ft R
  398. .sz 12
  399. \l'17.1c'
  400. .nf
  401.  
  402.     Transformation
  403.     of Attributed Trees
  404.     Using Pattern Matching
  405.  
  406.     J. Grosch
  407.  
  408.  
  409. \l'17.1c'
  410. .sp 12.5c
  411. \l'17.1c'
  412. .ft H
  413. .nf
  414.     GESELLSCHAFT F\*UR MATHEMATIK
  415.     UND DATENVERARBEITUNG MBH
  416.  
  417.     FORSCHUNGSSTELLE F\*UR
  418.     PROGRAMMSTRUKTUREN
  419.     AN DER UNIVERSIT\*AT KARLSRUHE
  420. .r
  421. \l'17.1c'
  422. .bp
  423. .\" .oh '''%'
  424. .\" .eh '''%'
  425. .ce 99
  426. .sz 20
  427. .b " "
  428. .sp 2
  429. Project
  430. .sp
  431. .b "Compiler Generation"
  432. .sp
  433. .sz 12
  434. \l'15c'
  435. .sp
  436. .sz 16
  437. .b "Transformation of Attributed Trees Using Pattern Matching"
  438. .sp 2
  439. Josef Grosch
  440. .sp 2
  441. .sz 14
  442. Aug. 28, 1991
  443. .sp
  444. .sz 12
  445. \l'15c'
  446. .sp 2
  447. Report No. 27
  448. .sp 2
  449. Copyright \(co 1991 GMD
  450. .sp 2
  451. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  452. Forschungsstelle an der Universit\*at Karlsruhe
  453. Vincenz-Prie\*snitz-Str. 1
  454. D-7500 Karlsruhe
  455. .ce 0
  456. .fi
  457. .if 0 \{\
  458. .nr $r 12    \" factor for vertical spacing
  459. .nr $R \n($r
  460. .bp
  461. .ce 99
  462. .b "Transformation of Attributed Trees Using Pattern Matching"
  463. .sp 2
  464. Josef Grosch
  465. GMD Forschungsstelle an der Universit\*at Karlsruhe
  466. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  467. +721-662226
  468. grosch@karlsruhe.gmd.de
  469. .sp 2
  470. \fBKeywords\fP transformation, attributed trees, pattern matching
  471. .ce 0
  472. .\}
  473. .oh '''%'
  474. .eh '''%'
  475. .bp 1
  476. .ce 99
  477. .b "Transformation of Attributed Trees Using Pattern Matching"
  478. .sp 2
  479. Josef Grosch
  480. GMD Forschungsstelle an der Universit\*at Karlsruhe
  481. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  482. +721-662226
  483. grosch@karlsruhe.gmd.de
  484. .ce 0
  485. .sp 2
  486. .uh Abstract
  487. This paper describes a tool for the transformation of attributed trees using pattern matching.
  488. The trees to be processed are defined by a formalism based on context-free grammars.
  489. Operations for trees such as composition and decomposition are provided.
  490. The approach can be characterized as an amalgamation of trees or terms including
  491. pattern matching, with recursion, attribute grammars, and imperative programming.
  492. Transformations can either modify the input trees or map them to arbitrary output.
  493. Possible applications are the various transformation tasks in compilers such as
  494. semantic analysis, optimization, or the generation of intermediate representations.
  495. The design goals have been to combine an expressive and high level technique for
  496. transformation with flexibility, efficiency, and practical usability.
  497. A reliable development style is supported by static typing and checks for the single
  498. assignment property of variables.
  499. We give some example transformations and describe the input language of our tool called
  500. .i puma .
  501. The relationship to similar work is discussed.
  502. Finally, experimental results are presented that demonstrate the efficiency of our approach.
  503. .uh Keywords
  504. transformation, attributed trees, pattern matching
  505. .sh 1 Introduction
  506. .lp
  507. The transformation of trees using pattern matching becomes an accepted technique.
  508. Several tools have been constructed recently that follow this principle
  509. \*([[CoP90\*(],HeS91\*(],LMW89\*(],Vol91\*(]].
  510. Tools for code generation successfully use the same technique, too
  511. \*([[AGT89\*(],ESL89\*(]]. We present a new tool called
  512. .i puma
  513. and its input language for the transformation and manipulation of attributed trees and graphs
  514. \*([[Gro91a\*(]].
  515. .i Puma
  516. stands for \fIp\fPattern \fIma\fPtching and \fIu\fPnification.
  517. Its intended application areas are the various transformation tasks in a
  518. compiler operating on abstract syntax trees or arbitrary graph structures. This includes
  519. semantic analysis, optimization, intermediate code generation, source-to-source translation,
  520. and eventually machine code generation.
  521. .pp
  522. The trees that are subject to pattern matching are described by a formalism based on
  523. context-free grammars. The tree nodes may be associated with attributes of arbitrary types.
  524. Node types are used to specify the properties of tree nodes. An extension mechanism induces
  525. a subtype relation among the node types. Pattern matching is extended to handle subtypes and
  526. attributes, too. Operations for the composition and decomposition of trees are supported by
  527. a concise notation.
  528. .pp
  529. The building blocks for a transformation are recursive subroutines, classified as
  530. procedures, functions, and predicates, with an arbitrary number of input and output
  531. parameters. The bodies of the subroutines consist of rules which are made
  532. up of patterns, conditions, statements, and expressions.
  533. The first two components control the applicability of a rule.
  534. The statements determine what has to be done whenever a rule is applicable.
  535. The expressions provide values for the output parameters and the function result.
  536. .pp
  537. Static type checking with respect to trees is provided. Variables are declared implicitly and
  538. they are checked for the single assignment property. There is read and write access to
  539. attributes stored in the tree which allows the construction of attribute evaluators.
  540. In all places it is possible to escape to hand-written code
  541. which provides the power and flexibility of the imperative programming style.
  542. .pp
  543. The output of the generator is a source module in one of the target languages C or Modula-2.
  544. This module allows for easy integration and cooperation with other modules, either
  545. hand-written or generated ones.
  546. The pattern matching is local and considers a region at the top of the current subtree, only.
  547. It is implemented by direct code and therefore efficient.
  548. .pp
  549. Our approach can be regarded from several points of view:
  550. From the point of view of imperative programming it is an extension by statically typed,
  551. attributed trees, constructs for composition and decomposition, and pattern matching.
  552. From the point of view of logic programming it omits backtracking and restricts pattern
  553. matching to one of the two terms being a ground term.
  554. It adds attributes which are stored in the terms
  555. (trees), static typing, input and output modes for parameters, and an easy escape to
  556. imperative features.
  557. From the point of view of functional programming it offers the simple style of
  558. functional programming which has always been present in imperative languages having
  559. functions and recursion. It adds the pattern matching facility.
  560. From the point of view of attribute grammars it allows the specification of attribute
  561. evaluation with explicit control of the evaluation order or visit sequences. This eases the
  562. use of global attributes and gives full control on side-effects.
  563. .pp
  564. The intended use of this tool proceeds in three steps:
  565. First, a tree is constructed either by a parser, a previous transformation phase, or whatever
  566. is appropriate.
  567. Second, the attributes in the tree are evaluated either using an attribute grammar based
  568. tool, by a
  569. .i puma
  570. specified tree traversal and attribute computations, or by hand-written code.
  571. Third, the attributed tree is transformed or mapped to another data structure by a
  572. .i puma
  573. generated transformation module.
  574. These steps can be executed one after the other or more or less simultaneously.
  575. Besides trees,
  576. .i puma
  577. can handle attributed graphs as well, even cyclic ones. Of course the cycles have to be
  578. detected in order to avoid infinite loops. A possible solution uses attributes as marks for
  579. nodes already visited.
  580. .pp
  581. A transformer module can make use of attributes in the following ways:
  582. If attribute values have been computed by a preceding attribute evaluator and are accessed
  583. in read only mode then this corresponds to the three step model explained above. A
  584. .i puma
  585. generated module can also evaluate attributes on its own. A further possibility is that an
  586. attribute evaluator can call
  587. .i puma
  588. subroutines in order to compute attributes. This is especially of interest when attributes
  589. depend on tree-valued arguments.
  590. .pp
  591. The tool supports two classes of tree transformations:
  592. .i mappings
  593. and
  594. .i modifications .
  595. Tree mappings map an input tree to arbitrary output data.
  596. The input tree is accessed in read only mode and left unchanged. Tree
  597. .i modifications
  598. change a tree by e. g. computing and storing
  599. attributes at tree nodes or by changing the tree structure. In this
  600. case the tree data structure serves as input as well as output and it
  601. is accessed in read and write mode.
  602. .pp
  603. The first class covers applications like the generation of
  604. intermediate languages or machine code. Trees are mapped to arbitrary
  605. output like source code, assembly code, binary machine code,
  606. linearized intermediate languages like P-Code, or another tree
  607. structure. A further variant of mapping is to emit a sequence of
  608. procedure calls which are handled by an abstract data type.
  609. .pp
  610. The second class covers applications like semantic analysis or
  611. optimization. Trees are decorated with attribute values, properties of
  612. the trees corresponding to context conditions are checked, or trees
  613. are changed in order to reflect optimizing transformations.
  614. .pp
  615. .i Puma
  616. is part of the Karlsruhe Toolbox for Compiler Construction\*([<\*([[GrE90\*(]]\*(>].
  617. In particular it cooperates with the generator for abstract syntax trees
  618. .i ast
  619. \*([[Gro91b\*(]] and the attribute evaluator generator
  620. .i ag
  621. \*([[Gro89\*(]]. The attributed trees are defined and managed by a module generated with
  622. .i ast .
  623. A second module generated by
  624. .i puma
  625. creates and handles these trees.
  626. This way all the powerful operations for trees and graphs provided by
  627. .i ast
  628. are available such as reader and writer procedures or the interactive browser.
  629. For sake of simplicity we will deviate from reality in this paper and treat the
  630. definition of the tree structure as part of
  631. .i puma .
  632. .pp
  633. The rest of this paper is organized as follows:
  634. Section 2 presents a few simple examples of how to describe transformations with
  635. .i puma .
  636. Section 3 describes the input language of the tool.
  637. Section 4 sketches the implementation of the generated transformer module.
  638. Section 5 compares our approach with related work.
  639. Section 6 presents experimental results.
  640. Section 7 contains concluding remarks.
  641. .sh 1 "Tree Transformation by Pattern Matching"
  642. .lp
  643. The probably easiest way to get an impression of our approach can be obtained by having a
  644. look at a few introductory examples. We will use the abstract syntax of simple arithmetic
  645. expressions as input data structure. Besides a few intrinsic attributes describing e. g. the
  646. values of constants we use an attribute called
  647. .i Type .
  648. It describes the type of every subexpression. Its domain are trees, too.
  649. The tree definition based on a context-free grammar shown
  650. in Example 1 specifies the structure of expressions and types.
  651. .(b I
  652. Example 1: Tree Definition
  653. .sp 0.5
  654. .FT
  655. Expr            = Type <
  656.    Plus         = Lop: Expr Rop: Expr .
  657.    Minus        = Lop: Expr Rop: Expr .
  658.    Const        = [Value] .
  659.    Adr          = <
  660.       Index     = Adr Expr .
  661.       Select    = Adr [Ident: tIdent] .
  662.       Ident     = [Ident: tIdent] .
  663.    >.
  664. >.
  665. Type            = <
  666.    Int          = .
  667.    Real         = .
  668.    Bool         = .
  669.    Array        = [Lwb] [Upb] Type .
  670.    Record       = Fields .
  671. >.
  672. Fields          = <
  673.    NoField      = .
  674.    Field        = [Ident: tIdent] Type Fields .
  675. >.
  676. .)b
  677. .pp
  678. The names before the character '=' can be regarded both as rule names or nonterminals.
  679. The possible right-hand sides for one nonterminal are enclosed in angle brackets '<' and '>'.
  680. Non-tree valued attributes are enclosed in square brackets '[' and ']'.
  681. The attributes
  682. .i Lwb ,
  683. .i Upb ,
  684. and
  685. .i Value
  686. are of the default type
  687. .i int .
  688. The attribute
  689. .i Ident
  690. is of the user-defined type
  691. .i tIdent .
  692. The tree-valued attribute
  693. .i Type
  694. of the rule named
  695. .i Expr
  696. is written like every other right-hand side nonterminal.
  697. The selector names
  698. .i Lop
  699. and
  700. .i Rop
  701. used in the rules called
  702. .i Plus
  703. and
  704. .i Minus
  705. allow symbolic access to right-hand side elements having the same type.
  706. .pp
  707. The association of an attribute such as
  708. .i Type
  709. with a nonterminal like
  710. .i Expr
  711. adds this attribute to every right-hand side belonging to this nonterminal. Hence the rules
  712. .i Plus
  713. and
  714. .i Minus
  715. have three right-hand side elements.
  716. .(z I
  717. Example 2: Generation of P-Code
  718. .sp 0.5
  719. .FT
  720. PROCEDURE P_Code (Tree)
  721. .sp 0.5
  722. Plus  (Int  (), Lop, Rop) :- P_Code (Lop); P_Code (Rop); Emit (ADDI); .
  723. Plus  (Real (), Lop, Rop) :- P_Code (Lop); P_Code (Rop); Emit (ADDR); .
  724. Minus (Int  (), Lop, Rop) :- P_Code (Lop); P_Code (Rop); Emit (SUBI); .
  725. Minus (Real (), Lop, Rop) :- P_Code (Lop); P_Code (Rop); Emit (SUBR); .
  726. .)z
  727. .pp
  728. The subroutine specification presented in Example 2 describes part of a transformation of
  729. expression trees to P-Code\*([<\*([[NAJ76\*(]]\*(>]. The procedure
  730. .i P_Code
  731. performs a recursive tree traversal. Its body consists of a sequence of rules. Every rule is
  732. made up of a pattern and a list of statements separated by ':-'.
  733. Whenever a pattern matches against the input parameter of the subroutine,
  734. the associated statement list is executed. The parameter of the procedure
  735. .i P_Code
  736. is of type
  737. .i Tree
  738. which means that every tree according to the tree definition is a legal argument. The
  739. procedure
  740. .i Emit
  741. is supposed to be an external subroutine that performs output.
  742. .(b I
  743. Example 3: Computation of Type Sizes
  744. .sp 0.5
  745. .FT
  746. FUNCTION TypeSize ([Type, Fields]) int
  747. .sp 0.5
  748. Int  ()              RETURN 4 .
  749. Real ()              RETURN 4 .
  750. Bool ()              RETURN 1 .
  751. Array (Lwb, Upb, T)  RETURN (Upb - Lwb + 1) * TypeSize (T) .
  752. Record (F)           RETURN TypeSize (F) .
  753. Field (_, T, F)      RETURN TypeSize (T) + TypeSize (F) .
  754. NoField ()           RETURN 0 .
  755. .)b
  756. .pp
  757. The function
  758. .i TypeSize
  759. in Example 3 transforms or maps trees to integer values. It is defined to
  760. operate on trees of types
  761. .i Type
  762. and
  763. .i Fields
  764. and it returns a value of a type named
  765. .i int .
  766. Again this subroutine performs a recursive tree traversal. Instead of producing a side-effect
  767. like in the previous example it represents a pure functional mapping and demonstrates the
  768. arithmetic expression capabilities of
  769. .i puma .
  770. The character '_' denotes a so-called don't care pattern.
  771. .(b I
  772. Example 4: Testing two Types for Compatibility
  773. .sp 0.5
  774. .FT
  775. PREDICATE IsCompatible ([Type, Fields], [Type, Fields])
  776. .sp 0.5
  777. Int  ()             , Int  ()              .
  778. Real ()             , Real ()              .
  779. Bool ()             , Bool ()              .
  780. Array (Lwb, Upb, T1), Array (Lwb, Upb, T2) :- IsCompatible (T1, T2); .
  781. Record (F1)         , Record (F2)          :- IsCompatible (F1, F2); .
  782. Field (_, T1, F1)   , Field (_, T2, F2)    :- IsCompatible (T1, T2);
  783.                                               IsCompatible (F1, F2); .
  784. .)b
  785. .pp
  786. Example 4 presents the predicate
  787. .i IsCompatible
  788. which can be seen as a boolean function. It operates on two parameters of types
  789. .i Type
  790. or
  791. .i Fields .
  792. Accordingly, every rule has two patterns for matching against the two arguments.
  793. The first three rules lead to a return value of true if both patterns match both arguments.
  794. The fourth rule returns true if the attributes
  795. .i Lwb
  796. and
  797. .i Upb
  798. of the two argument trees match (have the same value) and if the recursive call
  799. .i IsCompatible
  800. returns true for the two types
  801. .i T1
  802. and
  803. .i T2
  804. of the array elements. If none of the rules matches the predicate returns false.
  805. .(z I
  806. Example 5: Procedure with Input and Output Parameters
  807. .sp 0.5
  808. .FT
  809. PROCEDURE ResultType (Type, Type, Operator: int => Type)
  810. .sp 0.5
  811. Int  () , Int  () , { opPlus  } => Int  () .
  812. Real () , Real () , { opPlus  } => Real () .
  813. Int  () , Int  () , { opMinus } => Int  () .
  814. Real () , Real () , { opMinus } => Real () .
  815. .)z
  816. .pp
  817. The subroutine given in Example 5 has three input and one output parameter. It computes
  818. the result type of a binary expression which depends on the types of the operands and on the
  819. operator. The third pattern of every rule is enclosed in curly brackets '{ and '}'. This
  820. represents so-called target code which is more or less passed unchanged and unchecked
  821. to the generated module. In this case
  822. .i opPlus
  823. and
  824. .i opMinus
  825. are named constants encoding operators. Without the curly brackets they would be treated as
  826. pattern variables. The expression after the symbol '=>' describes the value of the output
  827. parameter in case of a successful match. It consists of a tree constructor which creates
  828. a tree having one node.
  829. .sh 1 "Specification Language"
  830. .lp
  831. The description of a tree transformation consists of the definition of attributed trees and a
  832. set of subroutines.
  833. .sh 2 "Tree Structure"
  834. .lp
  835. The structure of attributed trees or (directed) graphs is specified by a
  836. formalism based on context-free grammars. However, we primarily use the terminology of trees
  837. and types, here. A tree consists of
  838. .i nodes .
  839. A node may be related to other nodes in a so-called
  840. .i parent-child
  841. relation. Then the first node is called a
  842. .i parent
  843. node and the latter nodes are called
  844. .i child
  845. nodes. Nodes without a parent node are usually called
  846. .i root
  847. nodes, nodes without children are called
  848. .i leaf
  849. nodes.
  850. .pp
  851. The structure and the properties of nodes are described by
  852. .i "node types" .
  853. Every node belongs to a node type.
  854. A specification of a tree describes a finite number of node types.
  855. A node type specifies the names of the child nodes and the associated node
  856. types as well as the names of the attributes and the associated attribute types.
  857. .\" .sh 2 Children
  858. .pp
  859. Children are distinguished by
  860. .i selector
  861. names which have to be unambiguous within one node type.
  862. The children are of a certain node type. Example:
  863. .(b
  864. .FT
  865.    Plus      = Lop: Expr Rop: Expr .
  866.    Index     = Adr: Adr Expr: Expr .
  867. .)b
  868. The example introduces two node types called
  869. .i Plus
  870. and
  871. .i Index .
  872. A node of type 
  873. .i Plus
  874. has two children which are selected by the names
  875. .i Lop
  876. and
  877. .i Rop .
  878. Both children are of the node type
  879. .i Expr .
  880. If a selector name is equal to the associated name of the node type it can
  881. be omitted. Therefore, the node type
  882. .i Index
  883. can be abbreviated as follows:
  884. .(b
  885. .FT
  886.    Index     = Adr Expr .
  887. .)b
  888. .\" .sh 2 Attributes
  889. .pp
  890. As well as children, every node type can specify an arbitrary number of
  891. .i attributes
  892. of arbitrary types. Like children, attributes are characterized by a selector
  893. name and a certain type.
  894. The descriptions of attributes are enclosed in brackets '[' and ']'. The attribute types
  895. are given by names taken from the target language. Missing attribute types
  896. are assumed to be
  897. .i int
  898. or
  899. .i INTEGER
  900. depending on the target language (C or Modula-2).
  901. Children and attributes can be given in any order (see Example 1).
  902. .\" .sh 2 Extensions
  903. .pp
  904. To allow several alternatives for the types of children an
  905. .i extension
  906. mechanism is used. A node type may be associated with several other node types enclosed
  907. in angle brackets '<' and '>'. Then this node type is called
  908. .i base
  909. or
  910. .i super
  911. type and the associated types are called
  912. .i derived
  913. types or
  914. .i subtypes .
  915. A derived type can in turn be extended with no limitation of the nesting depth.
  916. The extension mechanism induces a subtype relation between node types denoted by the symbol
  917. \(ib . This relation is transitive.
  918. Where a node of a certain node type is required, either a node of this node type or a node of
  919. a subtype thereof is legal.
  920. .pp
  921. In Example 1
  922. .i Expr
  923. is a base type describing nodes with one child called
  924. .i Type .
  925. The node type
  926. .i Expr
  927. has four derived types called
  928. .i Plus ,
  929. .i Minus ,
  930. .i Const ,
  931. and
  932. .i Adr .
  933. The node type
  934. .i Adr
  935. is in turn extended by three derived types called
  936. .i Index ,
  937. .i Select ,
  938. and
  939. .i Ident .
  940. Where a node of type
  941. .i Expr
  942. is required, all mentioned node types are legal.
  943. Where a node of type
  944. .i Adr
  945. is required, nodes of the types
  946. .i Index ,
  947. .i Select ,
  948. or
  949. .i Ident
  950. are legal.
  951. Where a node of type
  952. .i Index
  953. is required, nodes of type
  954. .i Index
  955. are legal, only. The subtype relation is the transitive and reflexive closure of:
  956. .i
  957. Plus \(ib Expr, Minus \(ib Expr, Const \(ib Expr, Adr \(ib Expr,
  958. Index \(ib Adr, Select \(ib Adr, Ident \(ib Adr.
  959. .pp
  960. Besides extending the set of legal node types, the extension mechanism has
  961. the property of extending the children and attributes of the base type.
  962. The derived types possess the children and attributes of the base type.
  963. They may define additional children and attributes. In other words they
  964. .i inherit
  965. the structure of the base type.
  966. The selector names of all children and attributes in an extension hierarchy have to be distinct.
  967. The syntax has been designed this way in order to allow single inheritance, only.
  968. .pp
  969. In Example 1 nodes of type
  970. .i Expr
  971. have one child selected by the name
  972. .i Type .
  973. Nodes of type
  974. .i Plus
  975. have three children with the selector names
  976. .i Type ,
  977. .i Lop ,
  978. and
  979. .i Rop .
  980. .sh 2 Subroutines
  981. .lp
  982. A set of subroutines constitutes the main building blocks of a transformation.
  983. Like in programming languages, subroutines are parameterized
  984. abstractions of statements or expressions.
  985. There are three kinds of subroutines:
  986. .(b
  987. .ta 2c
  988. procedure    : a subroutine acting as a statement
  989. function    : a subroutine acting as an expression and returning a value
  990. predicate    : a boolean function
  991. .)b
  992. Subroutines are specified according to the following syntax:
  993. .(b
  994. .FT
  995. Subroutine = Header { Rule }
  996. Header     = PROCEDURE Ident ( [ Parameters ] [ => Parameters ] )
  997.            | FUNCTION  Ident ( [ Parameters ] [ => Parameters ] ) Type
  998.            | PREDICATE Ident ( [ Parameters ] [ => Parameters ] )
  999. Parameters = [ Ident : ] Type { , [ Ident : ] Type }
  1000. .)b
  1001. .lp
  1002. A subroutine consists of a header and a sequence of rules.
  1003. The header specifies the kind of the subroutine, its name, and its
  1004. parameters. In case of a function, the type of the result value is
  1005. added. Input and output parameters are separated by the symbol '=>'.
  1006. It suffices to give the type of a parameter. A name for the formal
  1007. parameter is optional.
  1008. .sh 2 Types
  1009. .lp
  1010. Types are either predefined in the target language like \fIint\fP and \fIINTEGER\fP,
  1011. or user-defined like \fIMyType\fP, or they are tree types like \fIExpr\fP.
  1012. A tree type is described by the name of a tree
  1013. definition, a single node type, or a list of node types enclosed in
  1014. brackets '[' and ']'. In case of ambiguities the latter two kinds may be
  1015. qualified by preceding the name of the tree definition.
  1016. .\" In every case a tree-type defines a set of legal node types. The name of a tree
  1017. .\" definition refers to every node type that is defined there. A single
  1018. .\" node type yields a set with just this one element and a list of node
  1019. .\" types yields the union of all list elements.
  1020. .(b
  1021. .\" Syntax:
  1022. .\" .sp 0.5
  1023. .FT
  1024. Type     = TreeType | UserType
  1025. TreeType = Ident | [ Ident . ] Ident | [ Ident . ] '[' Idents ']'
  1026. UserType = Ident
  1027. Idents   = Ident { , Ident }
  1028. .)b
  1029. .sh 2 Rules
  1030. .lp
  1031. A rule behaves like a branch in a case or switch statement. It consists
  1032. of a list of patterns, a list of expressions, a return expression in
  1033. case of a function, and a list of statements.
  1034. .\" The number of patterns must agree with the number of input parameters,
  1035. .\" and the types of the elements of those lists must be pairwise compatible.
  1036. .\" The number of expressions must agree with the number of output parameters,
  1037. .\" and the types of the elements of those lists must be pairwise compatible.
  1038. .\" The type of the expression after RETURN has to be compatible with the
  1039. .\" result type of a function.
  1040. .\" The type s of a pattern or an expression is said to be compatible
  1041. .\" to the type t of a formal parameter if s is a subtype of t (s \(ib t).
  1042. .(b
  1043. .\" Syntax:
  1044. .\" .sp 0.5
  1045. .FT
  1046. Rule     = [ Patterns ] [ => Exprs ] [ RETURN Expr ] :- { Statement ; } .
  1047. Patterns = Pattern { , Pattern }
  1048. Exprs    = Expr { , Expr }
  1049. .)b
  1050. .pp
  1051. The semantics of a rule is as follows:
  1052. A rule may succeed or fail.
  1053. It succeeds if all its patterns, statements, and expressions succeed \(\-
  1054. otherwise it fails. The patterns, statements, and expressions are
  1055. checked for success in the following order:
  1056. First, the patterns are checked from left to right. A pattern succeeds
  1057. if it matches its corresponding input parameter as described below.
  1058. Second, the statements are executed in sequence as long as they succeed.
  1059. The success of statements is defined below.
  1060. Third, the expressions are evaluated from left to right and
  1061. their results are passed to the corresponding output parameters.
  1062. In case of a function, additionally the expression after RETURN is
  1063. evaluated and its result is returned as value of the function call.
  1064. The success of expressions is defined below, too.
  1065. If all elements of a rule succeed then the rule succeeds and the subroutine returns.
  1066. If one element of a rule fails the process described above stops and
  1067. causes the rule to fail. Then the next rule is tried.
  1068. This search process continues until either a successful rule is found
  1069. or the end of the list is reached. In the latter case the behaviour
  1070. depends on the kind of the subroutine:
  1071. A procedure does nothing, a predicate returns false, and a function signals a runtime error.
  1072. There is one exception to this definition of the semantics which is explained later.
  1073. .sh 2 Patterns
  1074. .lp
  1075. A pattern describes the shape at the top or root of a subtree.
  1076. A pattern can be a decomposition of a tree, the keyword NIL,
  1077. a label or a variable, one of the don't care symbols '_' or '\fC\s-2..\s+2\fP',
  1078. or an expression. A decomposition is written as
  1079. a node type followed by a list of patterns in parenthesis '(' and ')'.
  1080. It may be optionally preceded by a label.
  1081. .(b L
  1082. .\" Syntax:
  1083. .\" .sp 0.5
  1084. .FT
  1085. Pattern = [ Ident : ] Ident ( [ Patterns ] ) | NIL | Ident | _ | .. | Expr
  1086. .)b
  1087. .lp
  1088. The match between a pattern and a value is defined recursively depending
  1089. on the kind of the pattern:
  1090. .pp
  1091. A decomposition with a node type t matches a tree u with a root node of type s if s is a
  1092. subtype of t (s \(ib t) and all subpatterns of t match their
  1093. corresponding subtrees or attributes of u.
  1094. If the node type is preceded by a label l then a binding is
  1095. established between l and u which defines the label l to refer to the tree u.
  1096. .pp
  1097. The first occurrence of a label l in a rule matches an arbitrary subtree
  1098. or attribute value u.
  1099. All further occurrences of the label l within patterns of this rule
  1100. match a subtree or an attribute value v only if u is equal to v.
  1101. The equality for trees is defined in the sense of structural equivalence.
  1102. Two attributes are equal if they have the same values.
  1103. A binding is established between l and u which defines the label l to refer to the value u.
  1104. The label can be used later to access the associated value.
  1105. .pp
  1106. The pattern NIL matches the values NULL or NIL.
  1107. The don't care symbol '_' matches one arbitrary subtree or attribute value.
  1108. The don't care symbol '\fC\s-2..\s+2\fP' matches any number of arbitrary subtrees or attribute values.
  1109. An expression matches a parameter or an attribute if both have the same values.
  1110. .\" .lp
  1111. .\" The ambiguity between a node type without a list of patterns in
  1112. .\" parentheses and a label is resolved in favor of the node type, by
  1113. .\" default. A node type t without a list of subpatterns is treated as t (\fC\s-2..\s+2\fP).
  1114. .\" .i Puma
  1115. .\" has an option that disables this behaviour. Then all node types require
  1116. .\" parentheses, otherwise they are considered as labels.
  1117. .sh 2 Expressions
  1118. .lp
  1119. Expressions denote the computation of values or the construction of trees.
  1120. Binary and unary operations as well as calls of external functions
  1121. are written as in the target language. Calls of
  1122. .i puma
  1123. functions and predicates distinguish between input and output arguments.
  1124. The syntax for tree composition is similar to the syntax of patterns.
  1125. .(b
  1126. .\" Syntax:
  1127. .\" .sp 0.5
  1128. .FT
  1129. Expr = Ident ( [ Exprs ] ) | NIL | Ident | _ | ..
  1130.      | Ident ( [ Exprs ] [ => Patterns ] )
  1131. .)b
  1132. .lp
  1133. The semantics of the different kinds of expressions is as follows:
  1134. .pp
  1135. A node type creates a tree node and provides the children and attributes
  1136. of this node with the values given in parenthesis.
  1137. .\" Again a missing list in parentheses is treated as (\fC\s-2..\s+2\fP).
  1138. NIL represents the value NULL or NIL.
  1139. A label refers to the expression it was bound to upon its definition.
  1140. .pp
  1141. A function or predicate call must be compatible with the corresponding definition in
  1142. terms of the numbers of expressions and patterns as well as their types.
  1143. A function call evaluates the expressions corresponding to input
  1144. parameters, passes the results to the function, and executes the
  1145. function. Upon return from the function the result value of the
  1146. function determines the result of this expression.
  1147. The values of the output parameters that the function returns are
  1148. matched against the actual patterns of the function call.
  1149. If one pair does not match the call fails.
  1150. Labels in the patterns may establish bindings that enable to refer to
  1151. the output parameters or subtrees thereof.
  1152. .pp
  1153. The don't care symbols specify that no computation should be executed,
  1154. either for one or for several expressions. The result values are undefined.
  1155. The binary and unary operators (prefix and postfix) of the
  1156. target language as well as array indexing, parentheses, numbers, and strings are known to
  1157. .i puma .
  1158. They are passed unchanged to the output.
  1159. .pp
  1160. In case of node types, labels for tree values, and functions returning
  1161. tree values,
  1162. .i puma
  1163. does type checking. For user types, target code
  1164. expressions, or target operators no type checking is done by
  1165. .i puma
  1166. but later by the compiler. An expression that does not contain calls of
  1167. .i puma
  1168. functions or predicates always succeeds. An expression containing those calls
  1169. succeeds if all the calls succeed \(\- otherwise it fails.
  1170. .sh 2 Statements
  1171. .lp
  1172. Statements are used to describe conditions, to perform output, to assign
  1173. values to attributes, and to control the execution of the transformer
  1174. via recursive subroutine calls. A statement is either a condition denoted
  1175. by an expression, a call of a procedure, an assignment, one of the
  1176. keywords REJECT or FAIL, or a target code statement. Every kind of
  1177. statement may succeed or fail as described below.
  1178. .(b
  1179. .\" Syntax:
  1180. .\" .sp 0.5
  1181. .FT
  1182. Statement    = Expr | Ident ( [ Exprs ] [ => Patterns ] ) | Ident := Expr
  1183.              | REJECT | FAIL | [ Declarations ] TargetCode
  1184. Declarations = Parameters 
  1185. .)b
  1186. .\" .pp
  1187. .\" There are two syntactic ambiguities: Target code in curly brackets { }
  1188. .\" is considered as target code statement instead of as target code
  1189. .\" expression. To obtain the latter meaning the expression should be
  1190. .\" enclosed in parentheses ( ).
  1191. .\" Subroutine calls are treated according to their declaration:
  1192. .\" Predicates and functions are treated as conditions,
  1193. .\" procedures and external subroutines are treated as procedure calls.
  1194. .\" If external subroutines should be considered as expressions the call should be
  1195. .\" enclosed in parentheses ( ), too.
  1196. .pp
  1197. Conditions are denoted by expressions and can be used to determine
  1198. properties that can not be expressed with pattern matching alone. Patterns describe
  1199. either shapes of a fixed size of a tree or the equality between two
  1200. values. Properties of trees of unlimited size and relations like '<', '<='
  1201. etc. have to be checked with conditions.
  1202. The expression has to be of type boolean or the call of a predicate.
  1203. .\" For a predicate call the same rules as for a function call apply.
  1204. A condition succeeds if the expression evaluates to true \(\- otherwise it fails.
  1205. .pp
  1206. For a procedure call the same rules as for a function call apply.
  1207. It succeeds if the values of all output parameters are matched by the
  1208. corresponding patterns \(\- otherwise it fails.
  1209. .\" A call of an undefined subroutine is treated as a call of a procedure
  1210. .\" that is defined externally. Such a call is flagged by a warning message.
  1211. .pp
  1212. An assignment statement evaluates its expression and stores this value
  1213. at the entity denoted by the identifier on the left-hand side. The
  1214. identifier can denote
  1215. a global or a local variable,
  1216. an input or an output parameter, as well as
  1217. a label for an attribute or a subtree.
  1218. An assignment statement succeeds if the expression succeeds \(\- otherwise it fails.
  1219. .pp
  1220. The statement REJECT does nothing but fail. This way the execution of the
  1221. current rule terminates and control is passed to the next rule.
  1222. The statement FAIL causes the execution of the current subroutine to
  1223. terminate. This statement is allowed in procedures and predicates, only.
  1224. Depending on the kind of subroutine the following happens:
  1225. A procedure terminates and a predicate returns false.
  1226. .pp
  1227. A target code statement which is enclosed in curly brackets '{' and '}'
  1228. is executed as in the target language. It can
  1229. be used to define labels by means of implementation language code or
  1230. calls of external subroutines. In this case the names of the labels and
  1231. their types have to be defined explicitly. This is done by declarations
  1232. written in the syntax of a parameter list that precede the target code statement.
  1233. .\" The user has to take care that all labels receive
  1234. .\" values within the target code statement using either assignments or via
  1235. .\" output parameters of subroutines.
  1236. A target code statement always succeeds.
  1237. .pp
  1238. Note, statements and expressions may cause side effects by changing e. g. global
  1239. variables, local variables, the input tree, or by producing
  1240. output. Those side effects are not undone when a rule fails.
  1241. .pp
  1242. Further features such as various possibilities concerning the use of hand-written target
  1243. code, named patterns instead of positional ones, or the definition of the equality or
  1244. matching operation between attributes by a macro mechanism are omitted for the
  1245. sake of brevity.
  1246. .sh 1 Implementation
  1247. .lp
  1248. From a given specification,
  1249. .i puma
  1250. generates a program module in one of the target languages C or Modula-2
  1251. implementing the desired transformation. The subroutines in the sense of
  1252. .i puma
  1253. are mapped to subroutines in the target language. Procedures
  1254. yield procedures, functions yield functions that return a value, and
  1255. predicates yield boolean functions. These subroutines can be called
  1256. from other modules using the usual subroutine call syntax of the target
  1257. language provided they are exported: All arguments are separated by commas \(\-
  1258. the symbol '=>' as separator between input and output arguments is only
  1259. required in calls processed by
  1260. .i puma .
  1261. .pp
  1262. The types of the parameters are treated as follows: Predefined types or
  1263. user defined types remain unchanged. Node types or sets of node types
  1264. are replaced by the name of the corresponding tree type.
  1265. This is a pointer to a union of record types. Input parameters are
  1266. passed by value and output parameters are passed by reference.
  1267. .pp
  1268. The rules of a subroutine are treated like a comfortable case or switch statement.
  1269. The code generated for pattern matching is relatively simple.
  1270. A naive implementation would just use a sequence of if statements.
  1271. This kind of code showed to be already rather efficient.
  1272. .i puma
  1273. optimizes the code with respect to the elimination of common tests for patterns and the
  1274. clever use of switch statements. Furthermore, tail recursion can be turned into iteration.
  1275. Labels are replaced by access paths to the associated values.
  1276. The code for the construction of tree nodes is inserted in-line.
  1277. It is therefore efficient because
  1278. no procedure calls are necessary for the creation of tree nodes.
  1279. .sh 1 "Related Research"
  1280. .lp
  1281. In this section we compare our approach with several programming paradigms and similar tools.
  1282. The intention is to provide further insight in the nature of our tool by looking at styles or
  1283. work the reader might be familiar with.
  1284. .sh 2 "Imperative Programming"
  1285. .lp
  1286. Our approach can be regarded as an extension of imperative languages by a type constructor
  1287. for trees. Operations
  1288. on trees for the composition and decomposition are provided using a concise term notation.
  1289. The storage management for trees is completely automatic. Intermediate variables for
  1290. output parameters of subroutines are declared implicitly and checked for the single
  1291. assignment property. Pattern matching represents a comfortable kind of case or switch
  1292. statement tailored towards processing of trees. This imperative view is reflected best by the
  1293. implementation of the generator
  1294. .i puma .
  1295. It can be seen as a preprocessor that provides attributed trees and pattern matching for
  1296. imperative languages.
  1297. .sh 2 "Logic Programming"
  1298. .lp
  1299. From the stand point of logic programming languages such as Prolog\*([<\*([[ClM84\*(]]\*(>]
  1300. our approach is relatively restricted and therefore one cannot classify
  1301. .i puma
  1302. as a logic programming language.
  1303. .i Puma
  1304. has no backtracking, no logic variables, and nothing like assert and retract. The
  1305. unification is unidirectional and restricted to one of the two terms being a ground term.
  1306. Similar are the syntax and the presence of predicates.
  1307. .i Puma
  1308. retains the "imperative subset" of Prolog. It turns out that this subset can be implemented
  1309. efficiently and it suffices to specify most of the transformation problems in compilers
  1310. \*([[Paa89\*(]].
  1311. .pp
  1312. Compared to Prolog the following features have been added:
  1313. Besides predicates there are procedures, functions, and customary expressions.
  1314. This allows for recursive functions and easy calls of
  1315. .i puma
  1316. subroutines from hand-written code. Attributes can be stored in the tree and accessed in read
  1317. and write mode. The terms or trees are statically typed. For parameters the modes input and
  1318. output are distinguished. Pattern matching is extended to cope with subtypes and attributes.
  1319. The modification of input terms is possible. Easy escape to hand-written code and cooperation
  1320. with other modules, either hand-written or generated, gives great flexibility and "imperative
  1321. power". The transformer modules including the pattern matching are translated to direct code
  1322. and therefore efficient.
  1323. .sh 2 "Functional Programming"
  1324. .lp
  1325. Compared to modern functional programming languages such as Hope\*([<\*([[BMS80\*(]]\*(>],
  1326. ML\*([<\*([[Mil85\*(]]\*(>], or Miranda\*([<\*([[Tur85\*(]]\*(>] our approach can of course not claim to
  1327. be functional. There is nothing like under or over supply of functions or higher-order
  1328. functions. It just supports the restricted kind of functional programming that can be found
  1329. in imperative languages having functions and recursion like e. g. C or Pascal. Even the
  1330. function results are restricted to simple data types and pointers. However, the latter allow
  1331. functions to return trees and graphs. With respect to the traditional functional language
  1332. Lisp\*([<\*([[MAE65\*(]]\*(>] our approach might be worth to be compared.
  1333. Whereas Lisp supports binary trees only,
  1334. .i puma
  1335. provides tree nodes with an arbitrary number of subtrees and attributes.
  1336. Dynamic typing and binding have
  1337. been replaced by their static counterparts. The pattern matching facility has been added.
  1338. .sh 2 "Attribute Grammars"
  1339. .lp
  1340. Our technique is related to attribute grammars
  1341. \*([[Knu68\*(],Knu71\*(]]
  1342. in several ways. Compared to pure attribute grammar processors such as
  1343. \*([[Gro89\*(],JoP90\*(],KHZ82\*(]]
  1344. there are some restrictions. In pure attribute grammar systems the attribute computations
  1345. are written in a functional notation. Knowing the dependencies among the attributes allows
  1346. the automatic (implicit) determination of an evaluation order for the attributes (visit
  1347. sequences). Furthermore it is possible to check an attribute grammar for completeness and
  1348. non-circularity.
  1349. Our approach is based on an explicit evaluation order using hand-written visit sequences.
  1350. Three kinds of data can be regarded as attributes: The "real" attributes stored in the tree,
  1351. the parameters of the subroutines, and global variables. This classification of the attributes
  1352. is done by the user. Whereas pure attribute grammars allow only computations local to a
  1353. grammar rule, the pattern matching facility makes computations on larger tree regions of
  1354. fixed size feasible. Considering attributes of the kind parameter and non-nested patterns
  1355. only, our approach is similar to affix grammars
  1356. \*([[Kos71\*(],Kos77\*(]]
  1357. or extended affix grammars\*([<\*([[Wat74\*(]]\*(>].
  1358. This holds from the syntactic as well as from the semantic point of view. A
  1359. .i puma
  1360. generated module can contribute to attribute evaluation in several ways:
  1361. First, the evaluation can be carried out completely by a transformation module itself using
  1362. one or more subroutines for traversing the tree.
  1363. Second,
  1364. .i puma
  1365. subroutines can be called as external subroutines from an attribute evaluator to compute
  1366. attributes \(\- especially those depending on tree-valued arguments.
  1367. The imperative or sequential style of
  1368. .i puma
  1369. allows simple control on side effects and easy production of arbitrary output.
  1370. .sh 2 "Optran"
  1371. .lp
  1372. The transformation tool Optran\*([<\*([[LMW89\*(]]\*(>]
  1373. has been designed for optimizing transformations. It is based on an attribute grammar and
  1374. modifies an input tree according to a given set of rules. A rule consists of a pattern,
  1375. conditions, and action statements. The actions can replace the tree part matched by the
  1376. pattern (where the unmatched subtrees might be reused) and compute new attribute values.
  1377. Optran emphasizes the automatic reevaluation of attributes\*([<\*([[LMO88\*(]]\*(>]
  1378. in order to arrive at attribute
  1379. values consistent with the specified attribute grammar. As the goals of Optran are rather
  1380. ambitious they pose several problems: In which order will the rules be applied and how to
  1381. find the locations in the tree where a pattern matches? When will the reevaluation of
  1382. attributes be carried out? The latter question is interesting because in the worst case
  1383. it will be necessary to recompute many attributes in a large part of the tree and therefore
  1384. consume a considerable amount of run time.
  1385. .pp
  1386. Our technique groups rules into an arbitrary number of subroutines. Every routine may perform
  1387. pattern matching on an arbitrary number of trees supplied as arguments not just one.
  1388. We explicitly control the execution order thus gaining an efficient and detailed way to
  1389. describe where and when what should happen.
  1390. .i Puma
  1391. is not concerned with reevaluation of attributes. Besides modification of the input
  1392. tree it also allows for mappings that produce arbitrary output.
  1393. .sh 2 "Trafola"
  1394. .lp
  1395. The functional language Trafola-H\*([<\*([[HeS91\*(]]\*(>]
  1396. was designed to be a specification language for program transformations. Besides all the
  1397. features one would expect from a modern functional language it has powerful constructs for
  1398. pattern matching. For example pattern matching is extended to cope with tuples and sequences.
  1399. This introduces nondeterminism which is handled using backtracking. The language is
  1400. statically typed and offers type polymorphism. Pattern matching is implemented by a
  1401. table-driven bottom up tree automata or by a backtracking algorithm. The functional
  1402. constructs are usually implemented by interpretation of an internal abstract machine.
  1403. Our approach does not aim to be functional but it retains the flexibility and efficiency of
  1404. imperative programming. Whereas the Trafola type constructor for sequences allows the grammar
  1405. for legal trees to be written in extended BNF,
  1406. .i puma
  1407. supports pure BNF, only. Both approaches allow so-called non linear patterns where a variable
  1408. occurs more than once in a pattern.
  1409. .i Puma
  1410. has extended pattern matching to handle subtypes.
  1411. .sh 2 "Codegenerator-Generators"
  1412. .lp
  1413. Tools for the generation of code generators such as
  1414. .i Twig
  1415. \*([[AGT89\*(]] or
  1416. .i Beg
  1417. \*([[ESL89\*(]] often use tree
  1418. pattern matching, too. In addition to a pattern, a condition, and an action a rule is
  1419. associated with costs. Pattern matching usually performs a global match on the complete input
  1420. tree in order to find a complete cover of the tree where the sum of all participating
  1421. rules is of minimal cost. Algorithms based on dynamic programming have proved to yield
  1422. satisfactory results. These tools are oriented towards code selection by transforming a
  1423. tree-like intermediate representation into machine code. Therefore there is de facto only one
  1424. subroutine with one tree-valued argument.
  1425. .i Beg
  1426. provides support for register allocation, has a fixed traversal scheme (post order),
  1427. and generates directly coded code-generators.
  1428. .i Twig
  1429. allows for the modification of the input tree, supports arbitrary traversal strategies, and
  1430. generates table-driven code-generators.
  1431. .sh 2 "Txl"
  1432. .lp
  1433. The tree transformation tool
  1434. .i txl
  1435. \*([[CaC91\*(],CoP90\*(]]
  1436. processes concrete syntax. It comprises a parser and an unparser for input and output of
  1437. trees and allows the generation of source-to-source translators. The tree transformation is
  1438. described by a set of rules consisting of a pattern, a condition, and a replacement. Usually
  1439. the user does not have to take care about the order or location of rule applications. Rules
  1440. are applied as long as there is one that matches. Thereby the tree is modified. There are
  1441. means to describe which set of rules should be applied to which subtrees. Patterns are not
  1442. written in a nested fashion but as strings containing nonterminals. The tool parses
  1443. these strings in order to recognize the nesting structure. As
  1444. .i puma
  1445. is oriented towards abstract trees, the transformers are independent of parsing or
  1446. unparsing. Besides tree modifications
  1447. .i puma
  1448. allows for tree mappings producing arbitrary output.
  1449. Another difference is the explicit control of the execution order which allows an efficient
  1450. implementation of the generated transformers.
  1451. .sh 1 "Experiences"
  1452. .lp
  1453. In a first real world application,
  1454. .i puma
  1455. was successfully used to generate a code-generator in a compiler for the robot control
  1456. language IRL\*([<\*([[IRL92\*(]]\*(>].
  1457. The front-end of this compiler constructs an abstract syntax tree which is decorated with
  1458. attributes during the semantic analysis phase. The code-generator maps this attributed tree to
  1459. the standardized robot control code IRDATA\*([<\*([[IRD91\*(]]\*(>]
  1460. which is comparable to assembly code. The strongly typed nature of IRDATA makes code-generation
  1461. harder than one would expect. For instance it is impossible to implement record variables
  1462. other than by turning every field into a separate variable. More complex types such as arrays
  1463. with elements of a record type have to be transformed into records containing arrays.
  1464. Nevertheless these nontrivial
  1465. problems could be solved relatively easy with appropriate transformation rules.
  1466. The code-generator uses a two phase scheme in order to deal with forward references.
  1467. The first phase selects IRDATA instructions and stores them in memory. The second phase
  1468. replaces symbolic labels by absolute ones, encodes the instructions, and writes the final
  1469. code to an output file. The data structure for storing the instructions in memory is managed
  1470. by a module generated by the tool
  1471. .i ast .
  1472. The development time was three months.
  1473. .(b
  1474. .ce
  1475. Table 1: Sizes of the Code-Generator Parts
  1476. .sp 0.5
  1477. .TS
  1478. center box;
  1479. l | c | c | c
  1480. l | c | c | c
  1481. l | n | n | n
  1482. .
  1483.      Specification    C Code    Binary Code
  1484.      [lines]    [lines]    [KB]
  1485. _
  1486. code selection (\fIpuma\fP)    3032    8600    111
  1487. instruction storage (\fIast\fP)    165    3430    36
  1488. output (hand-written)       -    700    7
  1489. _
  1490. total                         3197    12730    154
  1491. .TE
  1492. .)b
  1493. .pp
  1494. The parts of the code-generator have the sizes listed in Table 1.
  1495. The figures stem from measurements on a SPARC station ELC.
  1496. The complete compiler runs at speed of 1000 lines per second.
  1497. The run time is distributed among the phases as follows:
  1498. Scanning and parsing takes 21 %, semantic analysis 10 %, code-generation 18 %, and output of
  1499. the generated code 51 %. The huge share for the output comes from the voluminous nature of
  1500. IRDATA. The output reaches four times the size of the source program.
  1501. .sh 1 Conclusions
  1502. .lp
  1503. We presented a tool for the transformation of attributed trees using pattern matching.
  1504. It is based on the definition, composition, and decomposition of trees in combination with
  1505. recursion and pattern matching for trees as well as for attributes. It supports the mapping
  1506. of trees to arbitrary output as well as the modification of trees. Moreover it can be used to
  1507. construct attribute evaluators. The easy escape to an imperative programming language
  1508. assures flexibility and practical usability. The tool has been designed to provide an
  1509. expressive technique that can be implemented efficiently.
  1510. .pp
  1511. The tool
  1512. .i puma
  1513. and its predecessor called
  1514. .i Gentle
  1515. \*([[WGS89\*(]] have been used successfully in several real world projects.
  1516. At our institution a front-end for a C compiler and a compiler for a functional language have
  1517. been generated. An industrial company makes use of it for a language implementation project,
  1518. too. All applications report their satisfaction with this approach and relative short
  1519. development times. The interesting question is where does this success come from?
  1520. The final paragraphs give the author's subjective opinion.
  1521. .pp
  1522. First, there are several aspects that support a high level programming style.
  1523. The data type tree including operations for composition and decomposition replaces
  1524. the handling of pointers, records, and dynamic storage allocation.
  1525. Pattern matching offers a comfortable kind of case statement.
  1526. Once it is understood and accepted then recursion seems to be easier to deal with then
  1527. iteration.
  1528. The implicit declaration of variables simplifies coding.
  1529. The check for the single assignment property catches errors such as missing or multiple
  1530. computations.
  1531. A concise syntactic notation is probably more profitable than one would imagine.
  1532. (Many of the the mentioned arguments have contributed to the success of Lisp and Prolog.)
  1533. The approach supports an incremental development style: Initially, rules for the most general
  1534. form are supplied and later rules for special cases are added in order to improve
  1535. performance.
  1536. Furthermore static typing discovers many errors during generation time.
  1537. .pp
  1538. Second, the approach is designed to be very flexible and open.
  1539. Every combination of attribute processing from mere reading and matching of attributes to
  1540. complete evaluation can be expressed.
  1541. The method allows tree modifications as well as mappings that produce arbitrary output.
  1542. The explicit description of execution order gives full control on side effects.
  1543. The escape to imperative programming and the easy integration with external subroutines are
  1544. essential loopholes.
  1545. The tool as well as the generated code are efficient and can be used in production projects.
  1546. It is probably the combination of all the mentioned properties and reasons that 
  1547. we regard this approach to be very promising.
  1548. .fi
  1549. .sz 12
  1550. .[]
  1551. .[-
  1552. .ds [F AGT89
  1553. .ds [A A\*(p]\*(a]V\*(p] Aho
  1554. .as [A \*(c]M\*(p] Ganapathi
  1555. .as [A \*(m]S\*(p]\*(a]W\*(p]\*(a]K\*(p] Tjiang
  1556. .ds [T Code Generation Using Tree Matching and Dynamic Programming
  1557. .ds [J ACM Trans. Prog. Lang. and Systems
  1558. .ds [V 11
  1559. .ds [N 4
  1560. .nr [P 1
  1561. .ds [P 491-516
  1562. .ds [D Oct. 1989
  1563. .][
  1564. .[-
  1565. .ds [F BMS80
  1566. .ds [A R\*(p] Burstall
  1567. .as [A \*(c]D\*(p] MacQueen
  1568. .as [A \*(m]D\*(p] Sannella
  1569. .ds [T HOPE: An Experimental Applicative Language
  1570. .ds [I Computer Science Department, Edinburgh
  1571. .ds [R Report CSR-62-80
  1572. .ds [D 1980
  1573. .][
  1574. .[-
  1575. .ds [F CaC91
  1576. .ds [A I\*(p]\*(a]H\*(p] Carmichael
  1577. .as [A \*(n]J\*(p]\*(a]R\*(p] Cordy
  1578. .ds [T TXL - Tree Transformation Language, Syntax and Informal Semantics
  1579. .ds [I Dept. of Computing and Information Sciences, Queens's Univeristy, Kingston
  1580. .ds [D Apr. 1991
  1581. .][
  1582. .[-
  1583. .ds [F ClM84
  1584. .ds [A W\*(p]\*(a]F\*(p] Clocksin
  1585. .as [A \*(n]C\*(p]\*(a]S\*(p] Mellish
  1586. .ds [T Programming in Prolog
  1587. .ds [I Springer Verlag
  1588. .ds [C Berlin
  1589. .ds [D 1984
  1590. .][
  1591. .[-
  1592. .ds [F CoP90
  1593. .ds [A J\*(p]\*(a]R\*(p] Cordy
  1594. .as [A \*(n]E\*(p] Promislow
  1595. .ds [T Specification and Automatic Prototype Implementation of Polymorphic Objects in TURING using the TXL Dialect Processor
  1596. .ds [J Proc. IEEE 1990 International Conference on Computer Languages
  1597. .nr [P 1
  1598. .ds [P 145-154
  1599. .ds [D Mar. 1990
  1600. .ds [C New Orleans
  1601. .][
  1602. .[-
  1603. .ds [F ESL89
  1604. .ds [A H\*(p] Emmelmann
  1605. .as [A \*(c]F\*(p]\*(a]W\*(p] Schr\\*:oer
  1606. .as [A \*(m]R\*(p] Landwehr
  1607. .ds [T BEG - a Generator for Efficient Back Ends
  1608. .ds [J SI\&GPLAN Notices
  1609. .ds [V 24
  1610. .ds [N 7
  1611. .nr [P 1
  1612. .ds [P 227-237
  1613. .ds [D July 1989
  1614. .][
  1615. .[-
  1616. .ds [F Gro89
  1617. .ds [A J\*(p] Grosch
  1618. .ds [T Ag - An Attribute Evaluator Generator
  1619. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1620. .ds [R Compiler Generation Report No. 16
  1621. .ds [N 16
  1622. .ds [D Aug. 1989
  1623. .][
  1624. .[-
  1625. .ds [F GrE90
  1626. .ds [A J\*(p] Grosch
  1627. .as [A \*(n]H\*(p] Emmelmann
  1628. .ds [T A Tool Box for Compiler Construction
  1629. .ds [V 477
  1630. .ds [J LNCS
  1631. .ds [C Berlin
  1632. .ds [I Springer Verlag
  1633. .nr [P 1
  1634. .ds [P 106-116
  1635. .ds [D Oct. 1990
  1636. .][
  1637. .[-
  1638. .ds [F Gro91a
  1639. .ds [A J\*(p] Grosch
  1640. .ds [T Puma - A Generator for the Transformation of Attributed Trees
  1641. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1642. .ds [R Compiler Generation Report No. 26
  1643. .ds [N 26
  1644. .ds [D July 1991
  1645. .][
  1646. .[-
  1647. .ds [F Gro91b
  1648. .ds [A J\*(p] Grosch
  1649. .ds [T Tool Support for Data Structures
  1650. .ds [J Structured Programming
  1651. .ds [V 12
  1652. .nr [P 1
  1653. .ds [P 31-38
  1654. .ds [D 1991
  1655. .][
  1656. .[-
  1657. .ds [F HeS91
  1658. .ds [A R\*(p] Heckmann
  1659. .as [A \*(n]G\*(p] Sander
  1660. .ds [T Trafola-H Reference Manual
  1661. .ds [I Universit\\*:at des Saarlandes, Saarbr\\*:ucken
  1662. .ds [R Prospectra Project Report
  1663. .ds [D 1991
  1664. .][
  1665. .[-
  1666. .ds [F IRD91
  1667. .ds [A IRDATA
  1668. .ds [T Industrial Robot Data, DIN 66313
  1669. .ds [I Beuth-Verlag
  1670. .ds [C Berlin
  1671. .ds [D 1991
  1672. .][
  1673. .[-
  1674. .ds [F IRL92
  1675. .ds [A IRL
  1676. .ds [T Industrial Robot Language, DIN 66312
  1677. .ds [I Beuth-Verlag
  1678. .ds [C Berlin, to appear
  1679. .ds [D 1992
  1680. .][
  1681. .[-
  1682. .ds [F JoP90
  1683. .ds [A M\*(p] Jourdan
  1684. .as [A \*(n]D\*(p] Parigot
  1685. .ds [T Application Development with the FNC-2 Attribute Grammar System
  1686. .ds [V 477
  1687. .ds [J LNCS
  1688. .ds [C Berlin
  1689. .ds [I Springer Verlag
  1690. .nr [P 1
  1691. .ds [P 11-25
  1692. .ds [D Oct. 1990
  1693. .][
  1694. .[-
  1695. .ds [F KHZ82
  1696. .ds [A U\*(p] Kastens
  1697. .as [A \*(c]B\*(p] Hutt
  1698. .as [A \*(m]E\*(p] Zimmermann
  1699. .ds [T GAG: A Practical Compiler Generator
  1700. .ds [V 141
  1701. .ds [S LNCS
  1702. .ds [I Springer Verlag
  1703. .ds [C Heidelberg
  1704. .ds [D 1982
  1705. .][
  1706. .[-
  1707. .ds [F Knu68
  1708. .ds [A D\*(p]\*(a]E\*(p] Knuth
  1709. .ds [T Semantics of Context-Free Languages
  1710. .nr [P 1
  1711. .ds [P 127-146
  1712. .ds [J Mathematical Systems Theory
  1713. .ds [V 2
  1714. .ds [D June 1968
  1715. .ds [N 2
  1716. .][
  1717. .[-
  1718. .ds [F Knu71
  1719. .ds [A D\*(p]\*(a]E\*(p] Knuth
  1720. .ds [T Semantics of Context-free Languages: Correction
  1721. .nr [P 1
  1722. .ds [P 95-96
  1723. .ds [J Mathematical Systems Theory
  1724. .ds [V 5
  1725. .ds [D Mar. 1971
  1726. .][
  1727. .[-
  1728. .ds [F Kos71
  1729. .ds [A C\*(p]\*(a]H\*(p]\*(a]A\*(p] Koster
  1730. .ds [T Affix Grammars
  1731. .nr [P 1
  1732. .ds [P 95-109
  1733. .ds [B ALGOL 68 Implementation
  1734. .ds [E J\*(p]\*(a]E\*(p]\*(a]L\*(p] Peck
  1735. .nr [E 1
  1736. .ds [I North Holland
  1737. .ds [C Amsterdam
  1738. .ds [D 1971
  1739. .][
  1740. .[-
  1741. .ds [F Kos77
  1742. .ds [A C\*(p]\*(a]H\*(p]\*(a]A\*(p] Koster
  1743. .ds [T CDL: A Compiler Implementation Language
  1744. .ds [V 47
  1745. .ds [J LNCS
  1746. .ds [C Berlin
  1747. .ds [I Springer Verlag
  1748. .nr [P 1
  1749. .ds [P 341-351
  1750. .ds [D 1977
  1751. .][
  1752. .[-
  1753. .ds [F LMO88
  1754. .ds [A P\*(p] Lipps
  1755. .as [A \*(c]U\*(p] M\\*:oncke
  1756. .as [A \*(c]M\*(p] Olk
  1757. .as [A \*(m]R\*(p] Wilhelm
  1758. .ds [T Attribute (Re)evaluation in OPTRAN
  1759. .ds [V 26
  1760. .ds [J Acta Inf.
  1761. .nr [P 1
  1762. .ds [P 213-239
  1763. .ds [D 1988
  1764. .][
  1765. .[-
  1766. .ds [F LMW89
  1767. .ds [A P\*(p] Lipps
  1768. .as [A \*(c]U\*(p] M\\*:oncke
  1769. .as [A \*(m]R\*(p] Wilhelm
  1770. .ds [T OPTRAN - A Language/System for the Specification of Program Transformations, System Overview and Experiences
  1771. .ds [V 371
  1772. .ds [J LNCS
  1773. .ds [C Berlin
  1774. .ds [I Springer Verlag
  1775. .nr [P 1
  1776. .ds [P 52-65
  1777. .ds [D 1989
  1778. .][
  1779. .[-
  1780. .ds [F MAE65
  1781. .ds [A J\*(p] McCarthy
  1782. .as [A \*(c]P\*(p]\*(a]W\*(p] Abrahams
  1783. .as [A \*(c]D\*(p]\*(a]J\*(p] Edwards
  1784. .as [A \*(c]T\*(p]\*(a]R\*(p] Hart
  1785. .as [A \*(m]M\*(p]\*(a]I\*(p] Levin
  1786. .ds [T Lisp 1.5 Programmer's Manual
  1787. .nr [P 0
  1788. .ds [P 106
  1789. .ds [I MIT Press
  1790. .ds [C Cambridge, MA
  1791. .ds [D 1965
  1792. .][
  1793. .[-
  1794. .ds [F Mil85
  1795. .ds [A R\*(p] Milner
  1796. .ds [T The Standard ML Core Language
  1797. .ds [J Polymorphism
  1798. .ds [V 2
  1799. .ds [N 2
  1800. .ds [D 1985
  1801. .][
  1802. .[-
  1803. .ds [F NAJ76
  1804. .ds [A K\*(p]\*(a]V\*(p] Nori
  1805. .as [A \*(c]U\*(p] Ammann
  1806. .as [A \*(c]K\*(p] Jensen
  1807. .as [A \*(c]H\*(p]\*(a]H\*(p] N\\*:ageli
  1808. .as [A \*(m]C\*(p] Jacobi
  1809. .ds [T The Pascal-P Compiler: Implementation Notes
  1810. .nr [P 0
  1811. .ds [P 53
  1812. .ds [R Bericht 10
  1813. .ds [I Eidgen\\*:ossische Technische Hochschule
  1814. .ds [C Z\\*:urich
  1815. .ds [D July 1976
  1816. .][
  1817. .[-
  1818. .ds [F Paa89
  1819. .ds [A J\*(p] Paakki
  1820. .ds [T A Prolog-Based Compiler Writing Tool
  1821. .ds [E D\*(p] Hammer
  1822. .nr [E 1
  1823. .ds [B Proceedings of the Workshop on Compiler Compiler and High Speed Compilation
  1824. .ds [C Berlin, GDR
  1825. .nr [P 1
  1826. .ds [P 107-117
  1827. .ds [D 1989
  1828. .][
  1829. .[-
  1830. .ds [F Tur85
  1831. .ds [A D\*(p]\*(a]A\*(p] Turner
  1832. .ds [T Miranda: A Nonstrict Functional Language with Polymorphic Types
  1833. .ds [V 201
  1834. .ds [J LNCS
  1835. .ds [C Berlin
  1836. .ds [I Springer Verlag
  1837. .nr [P 1
  1838. .ds [P 1-16
  1839. .ds [D 1985
  1840. .][
  1841. .[-
  1842. .ds [F Vol91
  1843. .ds [A J\*(p] Vollmer
  1844. .ds [T The Compiler Construction System GENTLE
  1845. .ds [R GMD-Arbeitspapier Nr. 508
  1846. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1847. .ds [D Feb. 1991
  1848. .][
  1849. .[-
  1850. .ds [F WGS89
  1851. .ds [A W\*(p]\*(a]M\*(p] Waite
  1852. .as [A \*(c]J\*(p] Grosch
  1853. .as [A \*(m]F\*(p]\*(a]W\*(p] Schr\\*:oer
  1854. .ds [T Three Compiler Specifications
  1855. .ds [R GMD-Studie Nr. 166
  1856. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  1857. .ds [D Aug. 1989
  1858. .][
  1859. .[-
  1860. .ds [F Wat74
  1861. .ds [A D\*(p]\*(a]A\*(p] Watt
  1862. .ds [T Analysis Oriented Two Level Grammars
  1863. .ds [I University of Glasgow
  1864. .ds [R Ph. D. thesis
  1865. .ds [C Glasgow
  1866. .ds [D 1974
  1867. .][
  1868. .bp 1
  1869. .lp
  1870. .b Contents
  1871. .sp
  1872. .xp
  1873.